package com.explorati.LeetCode64.minimumpathsum;

/**
 * 64. Minimum Path Sum
 * 
 * @author explorati
 *
 */
public class Solution {
	public static int minPathSum(int[][] grid) {
		if (grid.length <= 0) {
			return 0;
		}
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[0].length; j++) {
				if (i == 0 && j == 0) {
					continue;
				}
				if (i == 0) {
					grid[i][j] += grid[i][j - 1];
					continue;
				}
				if (j == 0) {
					grid[i][j] += grid[i - 1][j];
					continue;
				}
				grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
			}
		}
		return grid[grid.length - 1][grid[0].length - 1];
	}

	public static void main(String[] args) {
		int[][] grid = { { 1, 3, 1 }, { 1, 5, 1 }, { 4, 2, 1 } };
		System.out.println(minPathSum(grid));
	}
}
